

public class MySingleList {

    static class ListNode {
        //一个节点包含 val 和 next
        public int val;//节点的值域
        public ListNode next;//下一个节点的地址


        //提供构造方法
        public ListNode(int val) {
            this.val = val;
        }
    }

    //对于链表本身来说，必须得有一个头结点
    public ListNode head;//指向当前链表的头节点

    public void createList() {
        //创建链表，让每个节点连起来即可
        ListNode n1 = new ListNode(12);
        ListNode n2 = new ListNode(23);
        ListNode n3 = new ListNode(34);
        ListNode n4 = new ListNode(45);
        ListNode n5 = new ListNode(56);

        //通过 next 建立节点之间的联系
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        this.head = n1;
    }

    //得到单链表的长度
    public int size() {
        int count = 0;

        //用 cur 来遍历链表
        ListNode cur = head;

        //cur == null说明链表遍历完了
        while (cur != null) {
            count++;
            cur = cur.next;//让 cur 指向下一个节点
        }

        return count;
    }

    //打印链表
    public void display() {
        ListNode cur = head;

        //遍历链表
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }

        System.out.println();
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = head;

        while (cur != null) {
            //遍历链表，找到了就返回 true
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        //找不到就返回 false
        return false;
    }

    //清空链表
    public void clear() {
        this.head = null;//头节点为null，就找不到其他结点了
    }


    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);

        if (head == null) {
            head = node;
            return;
        }
        //绑定后面的数据
        node.next = head;
        //更新头
        head = node;
    }

    //尾插法
    public void addLast(int data) {

        ListNode node = new ListNode(data);
        //如果 head 为 null ，说明链表没有结点
        if (head == null) {
            head = node;
            return;
        }

        ListNode cur = head;
        //找到链表的尾巴节点
        while (cur.next != null) {
            cur = cur.next;
        }
        //到了这里说明 cur 指向了尾巴节点
        //插入
        cur.next = node;

    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        // index 不合法，则不能插入
        if (index < 0 || index > size()) {
            return;
        }
        if (index == 0) {
            //头插法
            addFirst(data);
            return;
        }
        if (index == size()) {
            //尾插法
            addLast(data);
            return;
        }
        //中间位置
        ListNode cur = head;
        //走 index - 1 步,找到要删除结点位置的前一个结点
        int step = index - 1;
        while (step != 0) {
            cur = cur.next;
            step--;
        }
        //先绑定后面的数据
        ListNode node = new ListNode(data);
        node.next = cur.next;
        //再来插入
        cur.next = node;
    }


    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //空表删不了
        if (head == null) {
            return;
        }
        //如果是头节点
        if (head.val == key) {
            head = head.next;
            return;
        }
        //找到 key 节点的前一个节点
        ListNode prev = findKeySubOne(key);
        if (prev == null) {
            //说明不存在 key 节点的前一个节点
            return;
        } else {
            ListNode target = prev.next;// target 为要删除的节点
            //删除
            prev.next = target.next;
        }

    }

    private ListNode findKeySubOne(int key) {
        //空表
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        //找到要删除的前一个结点
        //必须得判断 cur.next 是否为空，不然有可能会空指针异常
        //如果 cur.next == null,那么 cur 已经是尾巴结点，就没有继续判断的必要了
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        //空表
        if (head == null) {
            return;
        }

        ListNode prev = head;// prev 为 del 的前一个
        ListNode del = head.next;// del 表示要删除的元素
        // del 不为空，说明还有，有可能要删除的节点
        while (del != null) {
            if (del.val == key) {
                //删除
                prev.next = del.next;
                //del往后走
                del = del.next;
            } else {
                //两个都往后走
                prev = del;
                del = del.next;
            }
        }
        //最后再来判断头节点
        if (head.val == key) {
            head = head.next;
        }
    }

}


